// https://www.lintcode.com/problem/majority-element-ii/

public class Solution {
    /*
     * @param nums: a list of integers
     * @return: The majority number that occurs more than 1/3
     */
    public int majorityNumber(List<Integer> nums) {
        // write your code here
        // 基本思想就是出现3个不同的数就消掉，而主元素因为数量大于1/3所以必定会保存下来。
        // 具体实现如下：
        // 1. 通过v1、v2和c1、c2记录当前的2个数和出现次数。
        // 2. 如果第三个数都不匹配，c1和c2各减1，代表删除1个。
        // 3. 如果匹配其中一个，计数加1。
        // 4. 最后剩下的v1、v2比较，返回数量更多的那个。
        int v1 = nums.get(0);
        int v2 = nums.get(1);
        int c1 = 0;
        int c2 = 0;
        for (Integer i : nums) {
            if (i == v1) {
                ++c1;
            } else if (i == v2) {
                ++c2;
            } else if (c1 == 0) {
                v1 = i;
                c1 = 1;
            } else if (c2 == 0) {
                v2 = i;
                c2 = 1;
            } else {
                --c1;
                --c2;
            }
        }
        c1 = 0;
        c2 = 0;
        for (Integer i : nums) {
            if (i == v1) {
                ++c1;
            } else if (i == v2) {
                ++c2;
            }
        }
        return (c1 >= c2) ? v1 : v2;
    }
}